import java.util.HashMap;

public class LRUCache {

    class MyQueueNode {
        MyQueueNode left;
        MyQueueNode right;
        int key;
        int value;

        public MyQueueNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public MyQueueNode() {
        }
    }

    int capacity;
    MyQueueNode dummyHead;
    MyQueueNode dummyEnd;
    HashMap<Integer, MyQueueNode> map;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead = new MyQueueNode();
        map = new HashMap<>();
        dummyEnd = new MyQueueNode();
        dummyHead.right = dummyEnd;
        dummyEnd.left = dummyHead;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            MyQueueNode node = map.get(key);
            updateNode(node);
            return node.value;
        } else return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            MyQueueNode node = map.get(key);
            node.value = value;
            updateNode(node);
        } else {
            if (map.size() == capacity) {
                MyQueueNode node = dummyHead.right;
                remove(node);
                map.remove(node.key);
            }
            MyQueueNode node = new MyQueueNode(key, value);
            map.put(key, node);
            add(node);
        }
    }

    public void remove(MyQueueNode node) {
        node.left.right = node.right;
        node.right.left = node.left;
    }

    public void add(MyQueueNode node) {
        dummyEnd.left.right = node;
        node.right = dummyEnd;
        node.left = dummyEnd.left;
        dummyEnd.left = node;
    }

    public void updateNode(MyQueueNode node) {
        remove(node);
        add(node);
    }
}
